#include <stdio.h>
#include "Graph.h"

/*
 * Checks if a vertex with the same name as "name" parameter exists in gr.
 */
int checkUniqueName(graph *gr, char* name) {
	int i;
	for (i = 0; i < gr->numofVertices; i++) {
		if (strcmp(name, gr->vertices[i]->name) == 0) {
			return ERROR; /*the name is not unique*/
		}
	}
	return OK;
}

/*
 * Initializes a new vertex object, and its adjacency list.
 */
vertex *initVertex(int id, char * name) {
	char *vertexName;
	vertex *tmpVertex;
	vertexName = (char*) malloc(strlen(name) + 1);
	if (vertexName == NULL) {
		fprintf(stderr,"Error: standard function malloc has failed\n");
		return ERROR;
	}
	strcpy(vertexName, name);/*copy vertex name*/
	tmpVertex = (vertex *) malloc(sizeof(vertex));
	if (tmpVertex == NULL) {
		fprintf(stderr,"Error: standard function malloc has failed\n");
		free(vertexName);
		return NULL;
	}
	tmpVertex->id=id;
	tmpVertex->degree = 0;
	tmpVertex->name = vertexName;
	tmpVertex->edges = (edgesList *) malloc(sizeof(edgesList));
	if (tmpVertex->edges == NULL) {
		fprintf(stderr,"Error: standard function malloc has failed\n");
		free(tmpVertex);
		free(vertexName);
		return NULL;
	}
	tmpVertex->edges->head = NULL;
	tmpVertex->cluster = NULL;
	return tmpVertex;
}

/*
 * Adds a vertex to the graph.
 */
int add_vertex(graph *gr, char *name) {
	vertex *ver;
	if (!checkUniqueName(gr, name)) {
		fprintf(stderr,"Error: cannot add vertex - vertex name is not unique\n");
		return OK;
	}
	ver = initVertex(gr->numofVertices, name); /* allocate vertex and set default values*/
	if (ver == NULL)
		return ERROR;
	gr->numofVertices++;
	if (gr->numofVertices == gr->verticesCapacity) /*double array size if needed*/
	{
		if (doubleVerticesArray(gr) == ERROR) {
			freeVertex(ver);
			return ERROR;
		}
	}
	gr->vertices[gr->numofVertices - 1] = ver;
	return OK;
}

/*
 * Adds an edge to the graph
 */
int add_edge(graph *gr, int vertex1ID, int vertex2ID, double weight) {
	vertex *vertex1;
	vertex *vertex2;
	edge *e;
    int tmpId;
    
	if (gr->numofVertices <= vertex1ID || gr->numofVertices <= vertex2ID) {
		fprintf(stderr,
				"Error: one of the vertices name doesn't exists, the edge %d-%d won't added\n",
				vertex1ID, vertex2ID);
		return OK;
	}
    
	if (vertex1ID == vertex2ID) {
		fprintf(stderr,"Error: Cannot add self edge");
		return OK;
	}
    
	if (weight > 1 || weight <= 0) {
		fprintf(stderr,"Error: cannot add edge- weight must be in the range 0-1");
		return OK;
	}
    if(vertex1ID > vertex2ID)
    {
        tmpId = vertex1ID;
        vertex1ID = vertex2ID;
        vertex2ID = tmpId;
    }
	vertex1 = gr->vertices[vertex1ID];
	vertex2 = gr->vertices[vertex2ID];
    
	if (isEdgeExists(vertex1, vertex2) != NULL) {
		fprintf(stderr,"Error: cannot add edge - edge already exists\n");
		return OK;
	}
    
	e = initEdge(vertex1, vertex2, weight);
	if (e == NULL)
		return ERROR;
	e->id = gr->numOfEdges;
	gr->numOfEdges++;
    if(gr -> numOfEdges == gr ->edgesCapacity)
    {
        if(doubleEdgesArray(gr) == ERROR)
        {
            free(e);
            return ERROR;
        }
    }
	if (addToList(vertex1->edges, e) == ERROR || addToList(vertex2->edges, e) == ERROR) {
		free(e);
		return ERROR;
	}
	vertex1->degree++;
	vertex2->degree++;
	gr->edges[gr->numOfEdges - 1] = e;
    gr -> totalWeight += e -> weight;
	return OK;
}

/*
 * Frees the resources of a given vertex.
 */
void freeVertex(vertex* ver) {
	free(ver->name);
	freeList(ver->edges);
	free(ver);
}

/*
 * Frees a list of items (edges).
 */
void freeList(edgesList *edgeList) {
	struct edgeListItem * prev;
	struct edgeListItem * first = edgeList->head;
	struct edgeListItem * current = edgeList->head;
    if(first != NULL)
    {
        while (current->next != first) {
            prev = current;
            current = current->next;
            free(prev);
        }
        free(current);
    }
}

/*
 * Doubles the capacity of the vertices array of a certain graph.
 */
int doubleVerticesArray(graph* gr) {
	vertex** tmpVertices = (vertex**) realloc(gr->vertices,
                                              2 * gr->numofVertices * sizeof(vertex *));
	if (tmpVertices == NULL) {
		fprintf(stderr,"Error: standard function realloc has failed\n");
		return ERROR;
	}
	gr->vertices = tmpVertices;
	gr->verticesCapacity *= 2;
	return OK;
}

/*
 * Adds an items to a list
 */
int addToList(edgesList* edgesList, edge* ed) {
	edgeListItem *edgeItem;
	edgeListItem *prev;
    
	edgeItem = (edgeListItem *) malloc(sizeof(edgeListItem)); /*create circular point to item */
	if (edgeItem == NULL) {
		fprintf(stderr,"Error: standard function malloc has failed\n");
		return ERROR;
	}
    
	edgeItem->next = edgeItem;
	edgeItem->prev = edgeItem;
	edgeItem->edgeData = ed;
	if (edgesList->head != NULL) {
		/*add new edge as last in edge list */
		prev = edgesList->head->prev;
		prev->next = edgeItem;
		edgeItem->prev = prev;
		edgesList->head->prev = edgeItem;
		edgeItem->next = edgesList->head;
	} else {
		edgesList->head = edgeItem;
	}
	return OK;
}

/*
 * Finds a vertex in graph gr with the name vertexName.
 */
vertex * getVertexByName(graph* gr, char* vertexName) {
	int i;
	for (i = 0; i < gr->numofVertices; i++) {
		if (strcmp(vertexName, gr->vertices[i]->name) == 0)
			return gr->vertices[i];
	}
	return NULL;
}

/*
 * Doubles the edges array of the graph
 */
int doubleEdgesArray(graph* gr) {
	edge** tmpEdges = (edge**) realloc(gr->edges,
                                       2 * gr->numOfEdges * sizeof(edge *));
	if (tmpEdges == NULL) {
		fprintf(stderr,"Error: standard function realloc has failed\n");
		return ERROR;
	}
	gr->edges = tmpEdges;
	gr->edgesCapacity *= 2;
	return OK;
}

/*
 * Checks if edge exists between v1 and v2 and return 1 if exists
 * */
edge * isEdgeExists(vertex* v1, vertex* v2) {
	vertex *tmpVertex;
	edgeListItem* edgeItem;
	edgeListItem *head;
	if (v1->degree > v2->degree) {
		tmpVertex = v1;
		v1 = v2;
		v2 = tmpVertex;
	}
	head = v1->edges->head;
	if (head == NULL)
		return NULL;
	if (isEdgeIncludesVertex(head->edgeData, v2->id))
		return head -> edgeData;
    
	edgeItem = head->next;
	while (edgeItem != head) {
		if (isEdgeIncludesVertex(edgeItem->edgeData, v2->id))
			return edgeItem -> edgeData;
		edgeItem = edgeItem->next;
	}
	return NULL;
}

/*
 * Initializes an edge
 */
edge * initEdge(vertex* v1, vertex* v2, double weight) {
	edge * tmpEdge = (edge*) malloc(sizeof(edge));
	if (tmpEdge == NULL) {
		fprintf(stderr,"Error: standard function malloc has failed\n");
		return NULL;
	}
	tmpEdge->vertex1 = v1;
	tmpEdge->vertex2 = v2;
	tmpEdge->weight = weight;
    tmpEdge -> isDeleted =0;
	return tmpEdge;
    
}

/*
 * Checks if a certain edge contains a certain vertexId
 */
int isEdgeIncludesVertex(edge* e, int vertexId) {
	return e->vertex1->id == vertexId || e->vertex2->id == vertexId;
}

/*
 * Create adjucency matrix with the weight for every possible edge
 */
double ** getAdjMatrix(graph* gr)
{
    int i,j;
    edge *currEdge;
    double ** tmpMatrix = (double**)malloc(sizeof(double*) * gr -> numofVertices);
    if(tmpMatrix == NULL)
    {
        fprintf(stderr,"Error: standard function malloc has failed\n");
        return NULL;
    }
    for(i = 0; i < gr -> numofVertices; i++)
    {
        tmpMatrix[i] = (double*)malloc(gr -> numofVertices * sizeof(double));
        if(tmpMatrix[i] == NULL)
        {
            fprintf(stderr,"Error: standard function malloc has failed\n");
            for (;i >0; i--) {
                free(tmpMatrix[i]);
            }
            free(tmpMatrix);
            return NULL;
        }
    }
    for (i=0; i < gr -> numofVertices; i++) {
        for (j=i; j < gr -> numofVertices; j++) {
            tmpMatrix[i][j] = -1 * (gr -> defaultWeigth);
        }
    }
    for (i=0 ;i < gr -> numOfEdges; i++) {
        currEdge = gr -> edges[i];
        if(currEdge != NULL)
        {
            if(currEdge ->vertex1 -> id > currEdge -> vertex2 -> id)
            {
                tmpMatrix[currEdge ->vertex2 ->id][currEdge ->vertex1 -> id] = currEdge -> weight;
            }
            else
            {
                tmpMatrix[currEdge ->vertex1 ->id][currEdge ->vertex2 -> id] = currEdge -> weight;
            }
        }
    }
    return tmpMatrix;
}

/*
 * Initializes graph with default values
 */
graph* initGraph(double defWeight) {
    
	vertex** tmpVertices;
	edge** tmpEdges;
	clusterInfo** tmpClusters;
	graph* tmpGraph = (graph*) malloc(sizeof(graph));
	if (tmpGraph == NULL) {
		fprintf(stderr,"Error: standard function malloc has failed");
		return NULL;
	}
    tmpGraph -> totalWeight = 0;
	tmpGraph->defaultWeigth = defWeight;
	tmpGraph->numofVertices = 0;
    tmpGraph->numOfEdges = 0;
    tmpGraph->numOfClusters = 0;
	tmpVertices = (vertex**) calloc(1, sizeof(vertex*));
	if (tmpVertices == NULL) {
		fprintf(stderr,"Error: standard function malloc has failed");
		free(tmpGraph);
		return NULL;
	}
	tmpGraph->vertices = tmpVertices;
	tmpGraph->verticesCapacity = 1;
	tmpEdges = (edge**) calloc(1, sizeof(edge*));
	if (tmpEdges == NULL) {
		fprintf(stderr,"Error: standard function malloc has failed");
		free(tmpVertices);
		free(tmpGraph);
		return NULL;
	}
	tmpGraph->edgesCapacity = 1;
	tmpGraph->edges = tmpEdges;
	tmpClusters = (clusterInfo**) calloc(1, sizeof(clusterInfo*));
	if (tmpClusters == NULL) {
		fprintf(stderr,"Error: standard function malloc has failed");
		free(tmpVertices);
		free(tmpEdges);
		free(tmpGraph);
		return NULL;
	}
	tmpGraph->clustersCapacity = 1;
	tmpGraph->clusters = tmpClusters;
	return tmpGraph;
}

/*
 * free the cluster object of graph
 */
void freeClusters(graph *gr)
{
    int i;
    for (i=0; i < gr -> numOfClusters; i++) {
        free(gr -> clusters[i]);
    }
    
}

/*
 * free the graph object include its properties
 */
void free_graph(graph *gr)
{
    int i;
    for (i=0; i< gr -> numofVertices; i++) {
        freeVertex(gr -> vertices[i]);
    }
    for (i=0; i < gr -> numOfEdges; i++) {
        if(gr -> edges[i] != NULL)
            free(gr -> edges[i]);
    }
    freeClusters(gr);
    free(gr);
}

/*
 * free the edges adj matrix
 */
void freeAdjMatrix(double** matrix,int size)
{
    int i;
	for (i=0;i<size;i++){
		free(matrix[i]);
	}
	free(matrix);
    
}

/*
 * add the removed flag to edge that dosen't included in solution
 */
void removeEdge(graph* gr,int vertex1Id,int vertex2Id)
{
    vertex* vertex1;
    vertex *vertex2;
    edge* ed;
    vertex1 = gr -> vertices[vertex1Id];
    vertex2 = gr -> vertices[vertex2Id];
    vertex1->degree--;
    vertex2->degree--;
    ed= isEdgeExists(vertex1,vertex2);
    if(ed ==NULL)
        return;
    ed -> isDeleted =1;
}

/*
 * add new cluster to graph
 */
int addCluster(graph* gr, clusterInfo* cluster){
	clusterInfo** tmpClusters;
	if (gr->numOfClusters>=gr->clustersCapacity){
		tmpClusters = (clusterInfo**)realloc(gr->clusters,
                                             2 * gr->numOfClusters*sizeof(clusterInfo*));
		if (tmpClusters == NULL){
			fprintf (stderr, "Error: standard function malloc has failed\n");
			return ERROR;
		}
		gr->clusters = tmpClusters;
		gr->clustersCapacity*=2;
	}
	gr->clusters[gr->numOfClusters]=cluster;
	gr->numOfClusters+=1;
	return OK;
}

/*
 * add vertex to BFS queue
 */
int enqueueVertex(vertexQueue* q, vertex* v, int distance){
	vertexQueueItem* queueItem = malloc(sizeof(vertexQueueItem));
	if (q == NULL){
		fprintf (stderr, "Error: standard function malloc has failed\n");
		return ERROR;
	}
	queueItem->vertexData = v;
	queueItem->next = NULL;
	queueItem->distance = distance;
	if (q->head == NULL){
		q->head = q->last = queueItem;
	} else {
		q->last->next = queueItem;
		q->last = queueItem;
	}
	return OK;
}

/*
 * remove the next element from queue
 */
vertexQueueItem* dequeueVertex(vertexQueue* q){
	vertexQueueItem* vqi;
	if (q->head == NULL){
		return NULL;
	}
	vqi = q->head;
	q->head = q->head->next;;
	return vqi;
}

/*
 * insert vertex into queue if the BFS didn't discovered it already
 */
int enqueueIfNotDiscovered(vertexQueue* vQueue, int* discoveredVerticesArr, vertex* v, int vertexDistance){
	if(!discoveredVerticesArr[v->id]){
		if (!enqueueVertex(vQueue, v, vertexDistance)){
			return ERROR;
		}
		discoveredVerticesArr[v->id]=1;
	}
	return OK;
}

/*
 * clear and free the vertex queue
 */
void freeVertexQueue(vertexQueue* q){
	if (q != NULL){
		vertexQueueItem* vqi = q->head;
		vertexQueueItem* tmpItem;
		while (vqi != NULL){
			tmpItem = vqi->next;
			free(vqi);
			vqi = tmpItem;
		}
		free(q);
	}
}
